package wj.d909;

import java.util.ArrayList;
import java.util.List;

public class P1 {


    public int solve(int[] nums, int[] colors, int n, int k) {
        int[] count = new int[1];
        backTrack(nums, colors, 0, n, k, new ArrayList<>(), count);
        return count[0];
    }

    // 0红1蓝
    private void backTrack(int[] nums, int[] colors, int begin, int n, int k, List<Integer> savedList, int[] count) {
        if (begin == n) {//选择完成
            if (savedList.size() == 0) {
                return;
            }
            int[] diff = new int[2];
            int total = 0;
            for (int idx : savedList) {
                total += nums[idx];
                diff[colors[idx]] += 1;
            }
            System.out.println(savedList);
            //判断
            if (total % 3 == 0 && Math.abs(diff[0] - diff[1]) <= k) {
                count[0] += 1;
            }
        } else {
            //选
            savedList.add(begin);
            backTrack(nums, colors, begin + 1, n, k, savedList, count);
            savedList.remove(savedList.size() - 1);
            //不选
            backTrack(nums, colors, begin + 1, n, k, savedList, count);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 5, 5};
        int[] colors = new int[]{1, 0, 1};
        int n=3;
        int k=2;
        int count = new P1().solve(nums, colors, n, k);
        System.out.println(count);
    }
}
